package cn.edu.bjut.my.thinkinjava._20200501_02_DynamicProgram;

/**
 * 本例测试实现求取最长递增子序列
 * 数组？双指针
 * 子串？滑动窗口？？？但是好像不能解决递增的问题
 * 动态规划？
 * --含有子问题？好像有
 * --子问题重叠？似乎是
 * --状态转移方程？    大于时，+1 不大于时不变
 * ---状态:  也就是原问题和子问题中变化的变量
 * ---选择：种类 也就是对于每个状态，可以做出什么选择改变当前状态
 * dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度
 */
public class _02LongestIncreasingSubsequence {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length + 1];

        for (int i = 0; i < dp.length; i++) {
            dp[i] = 1;
        }

        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int res = 0;
        for (int i = 0; i < dp.length; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    public static void main(String[] args) {
        int[] array = {10,9,2,4,3,7,101,18};
        _02LongestIncreasingSubsequence lis = new _02LongestIncreasingSubsequence();
        int i = lis.lengthOfLIS(array);
        System.out.println(i);
    }
}
